using BepuUtilities;
using BepuUtilities.Collections;
using BepuUtilities.Memory;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading;

namespace BepuPhysics
{
    /// <summary>
    /// 处理将约束从索引较高的批移动到索引较低的批中,以避免累积不必要的ConstraintBatch。
    /// </summary>
    public class BatchCompressor
    {
        // 我们想要尽可能快地保持移除。因此,在删除约束时,不会尝试将约束从更高的约束批次拉到显示的槽中。
        // 随着时间的推移,这可能会导致大量额外的约束批处理,从而破坏多线程性能。
        // 这种批量压缩机在多个机架上解决了这个问题。
        // 专用批处理分析有一些非常好的优势：
        // 0)删除停留(相对)快速-无O(N)搜索或复杂逻辑。
        // 1)在混乱的冲突中,高流失率的添加/移除是非常常见的,这正是您需要尽可能少的开销的时候。
        // 1.5)高流失率的情况往往会迅速使极端激进的移出掉期的"优化"努力失效。
        // 2)由于其他参考阻塞,ON-Remove通常无法进行任何更改。
        // 3)专用批量分析可以跨多个帧延迟,因为中间结果从正确的角度来看都是好的。
        // 3.5)无论发生什么类型的添加/删除流失,递延成本都可以始终保持在较低水平。
        // 4)专用批处理分析可以异步执行,并隐藏在不是求解器且不修改求解器的其他静态阶段(如宽阶段、中期阶段)。
        // 5)即使我们处于"次优"约束配置中(即存在一些下拉),也很少会对性能产生影响,除非它实际导致额外的批处理。
        // 6)专用分析可以执行更复杂的启发式方法来优化批次。这不会做任何聪明的事情,但从理论上讲,它可以做到。

        // 请注意,这是试图用严格的贪婪方法解决NP困难问题(图的边着色),因此不会产生最佳结果。
        // (实际上,它可以使用的批次几乎是最佳批次的两倍！)
        // 稍后可能会提出一种稍微更聪明的方法-考虑到BVH SAH优化也是NP困难的,但是
        // 宽阶段的增量优化做得非常好(而且比纯粹的贪婪方法要好得多)。我们很可能可以创造一些东西
        // 和这里差不多。一些可能性：
        // 1)从每个批处理中随机获取N个约束集,推测性地将它们全部移除,并用更昂贵的本地
        // 优化器。重新配料必须考虑到每个级别的批次中所代表的所有其他机构。不能保证这一点
        // 除非"重新分批"算法被证明比贪婪算法更好,并且您有足够大的重新分批区域,否则不会取得进展。
        // 2)通过遍历约束图的一个区域来声明该区域。在其上执行Misra&Gries或类似的非指数脱机操作。
        // 3)可以要求较小的区域,并使用最优(指数)算法。我怀疑覆盖大片区域会更好。
        // 这类似于BVH细化中的小树旋转。

        // (请记住,就解算时间而言,最佳着色和贪婪着色之间的差异非常小。
        // 预计影响不到5%。换句话说,当有这么多其他选择可以追求的时候,花一个月的时间在一个研究项目上是不值得的。)

        public Solver Solver { get; private set; }
        public Bodies Bodies { get; private set; }
        float targetCandidateFraction;
        float maximumCompressionFraction;
        /// <summary>
        /// 获取或设置要分析的所需候选数,作为约束总数的一小部分。
        /// </summary>
        public float TargetCandidateFraction
        {
            get { return targetCandidateFraction; }
            set
            {
                if (value < 0 || value > 1) throw new ArgumentException("Fraction must be from 0 to 1.");
                targetCandidateFraction = value;
            }
        }
        /// <summary>
        /// 获取或设置在一次压缩执行中可以发生的最大约束移动数,它是约束总数的一部分。
        /// </summary>       
        public float MaximumCompressionFraction
        {
            get { return maximumCompressionFraction; }
            set
            {
                if (value < 0 || value > 1) throw new ArgumentException("Fraction must be from 0 to 1.");
                maximumCompressionFraction = value;
            }
        }
        struct Compression
        {
            public ConstraintHandle ConstraintHandle;
            public int TargetBatch;
        }
        struct AnalysisRegion
        {
            public int TypeBatchIndex;
            public int StartIndexInTypeBatch;
            public int EndIndexInTypeBatch;
        }
        /// <summary>
        /// 要优化的约束批次的索引。
        /// </summary>
        int nextBatchIndex;
        int nextTypeBatchIndex;

        // 请注意,这些列表在帧之间不包含任何有效信息-它们仅在优化期间存在。
        // 请注意,我们按需分配所有上下文及其压缩。它都是指针支持的,所以不用担心GC引用跟踪。
        Buffer<QuickList<Compression>> workerCompressions;
        IThreadDispatcher threadDispatcher;
        int analysisJobIndex;
        QuickList<AnalysisRegion> analysisJobs;


        Action<int> analysisWorkerDelegate;
        public BatchCompressor(Solver solver, Bodies bodies, float targetCandidateFraction = 0.01f, float maximumCompressionFraction = 0.0005f)
        {
            this.Solver = solver;
            this.Bodies = bodies;
            TargetCandidateFraction = targetCandidateFraction;
            this.MaximumCompressionFraction = maximumCompressionFraction;
            analysisWorkerDelegate = AnalysisWorker;
        }



        void AnalysisWorker(int workerIndex)
        {
            int jobIndex;
            while ((jobIndex = Interlocked.Increment(ref analysisJobIndex)) < analysisJobs.Count)
            {
                DoJob(ref analysisJobs[jobIndex], workerIndex, threadDispatcher.GetThreadMemoryPool(workerIndex));
            }
        }


        // 请注意,我们在概念上划分了查找和应用阶段,只是因为它们很有可能被安排在不同的时间。
        // 也就是说,虽然可以并行运行分析阶段,但不能并行运行应用程序。因此,如果您可以将顺序应用程序隐藏在一个不相关的
        // 阶段,这可能是一场净胜利。但是,在另一个并行分析阶段之上超额订阅另一个并行分析阶段可能并不明智。
        // 这只需要一些测试。
        // (宽泛阶段很可能是此覆盖的候选者-它既不会引起约束变化,而且与大多数其他阶段相比非常稳定。)

        unsafe void DoJob(ref AnalysisRegion region, int workerIndex, BufferPool pool)
        {
            ref var compressions = ref this.workerCompressions[workerIndex];
            ref var batch = ref Solver.ActiveSet.Batches[nextBatchIndex];
            var typeBatchIndex = region.TypeBatchIndex;
            ref var typeBatch = ref batch.TypeBatches[typeBatchIndex];
            var typeProcessor = Solver.TypeProcessors[typeBatch.TypeId];

            // 每个作业仅在单个类型批处理的子集上工作。
            var bodiesPerConstraint = typeProcessor.BodiesPerConstraint;
            var bodyHandles = stackalloc int[bodiesPerConstraint];
            ActiveConstraintBodyHandleCollector handleAccumulator;
            handleAccumulator.Bodies = Bodies;
            handleAccumulator.Handles = bodyHandles;
            var bodyHandlesSpan = new Span<int>(bodyHandles, bodiesPerConstraint);
            for (int i = region.StartIndexInTypeBatch; i < region.EndIndexInTypeBatch; ++i)
            {
                // 检查是否可以删除此约束。
                handleAccumulator.Index = 0;
                typeProcessor.EnumerateConnectedBodyIndices(ref typeBatch, i, ref handleAccumulator);
                for (int batchIndex = 0; batchIndex < nextBatchIndex; ++batchIndex)
                {
                    // 批次索引永远不会是回退批次,因为回退批次是最后一个批次(如果存在的话)。所以使用批引用句柄是安全的。
                    if (Solver.batchReferencedHandles[batchIndex].CanFit(bodyHandlesSpan))
                    {
                        compressions.Add(new Compression { ConstraintHandle = typeBatch.IndexToHandle[i], TargetBatch = batchIndex }, pool);
                        break;
                    }
                }
            }
        }

        struct CompressionTarget
        {
            public ushort WorkerIndex;
            public ushort Index;
            public ConstraintHandle ConstraintHandle;
        }
        struct CompressionComparer : IComparerRef<CompressionTarget>
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public int Compare(ref CompressionTarget a, ref CompressionTarget b)
            {
                return a.ConstraintHandle.Value.CompareTo(b.ConstraintHandle.Value);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private unsafe void ApplyCompression(int sourceBatchIndex, ref ConstraintBatch sourceBatch, ref Compression compression)
        {
            // 这里要小心：这是为了不执行无意义的复制而提供的引用,但您不能在传输完成后依赖它具有相同的值。
            ref var constraintLocation = ref Solver.HandleToConstraint[compression.ConstraintHandle.Value];
            var typeProcessor = Solver.TypeProcessors[constraintLocation.TypeId];
            if (sourceBatchIndex == Solver.FallbackBatchThreshold)
            {
                // 我们正在优化后备批,因此需要小心压缩相互干扰。平行分析假设每批
                // 最多包含每个正文的一个实例,这不适用于备用批。
                // 足够容易解决：检查目标批处理是否仍然可以保持约束。
                var bodyHandles = stackalloc int[typeProcessor.BodiesPerConstraint];
                ActiveConstraintBodyHandleCollector handleAccumulator;
                handleAccumulator.Bodies = Bodies;
                handleAccumulator.Handles = bodyHandles;
                handleAccumulator.Index = 0;
                Solver.EnumerateConnectedBodies(compression.ConstraintHandle, ref handleAccumulator);
                if (!Solver.batchReferencedHandles[compression.TargetBatch].CanFit(new Span<int>(bodyHandles, typeProcessor.BodiesPerConstraint)))
                {
                    // 回退批处理中的另一个压缩阻止了此压缩。
                    // 请注意,这并不是真正的问题-批量压缩是一个增量过程。如果可以进行其他压缩,将来的帧将很快找到它。
                    return;
                }
            }
            // Console.WriteLine($"COMPRESSING：{COMPRESSIO.ConstraintHandle}正在从{Solver.Batches.IndexOf(SourceBatch)}移动到{compression.TargetBatch}");

            // 请注意,我们不会简单地删除并重新添加约束;虽然这样可以工作,但它会重做许多不必要的工作。
            // 相反,因为我们已经确切地知道约束在哪里以及它应该去哪批约束,所以我们可以避免很多抽象
            // 做更多的直接复印。
            Solver.TypeProcessors[constraintLocation.TypeId].TransferConstraint(
                ref sourceBatch.GetTypeBatch(constraintLocation.TypeId), nextBatchIndex, constraintLocation.IndexInTypeBatch, Solver, Bodies, compression.TargetBatch);
        }

        /// <summary>
        /// 增量查找并应用一组压缩以应用于求解器批处理中的约束。
        /// 只要有可能,较高索引批处理中的约束就会尝试移动到较低索引批处理。
        /// </summary>
        public void Compress(BufferPool pool, IThreadDispatcher threadDispatcher = null, bool deterministic = false)
        {
            var workerCount = threadDispatcher != null ? threadDispatcher.ThreadCount : 1;
            var constraintCount = Solver.ActiveSet.ConstraintCount;
            // 如果没有要压缩的约束,则提前退出。在后续的一些阶段中假定存在约束,因此这不仅仅是一个优化。
            if (constraintCount == 0)
                return;
            var maximumCompressionCount = (int)Math.Max(1, Math.Round(MaximumCompressionFraction * constraintCount));
            var targetCandidateCount = (int)Math.Max(1, Math.Round(TargetCandidateFraction * constraintCount));

            pool.Take(workerCount, out workerCompressions);
            for (int i = 0; i < workerCount; ++i)
            {
                // 请注意：作业可能需要调整压缩计数列表中的大小。这需要使用每个员工的池。
                workerCompressions[i] = new QuickList<Compression>(Math.Max(8, maximumCompressionCount), threadDispatcher == null ? pool : threadDispatcher.GetThreadMemoryPool(i));
            }

            // 在任何给定的压缩尝试中,我们只优化一个ConstraintBatch。
            // 这保证了在压缩过程中发生的每个优化
            // 不影响任何其他优化,因为ConstraintBatch保证主体仅由单个约束引用。
            // 这在多线程时很有用-我们不必担心其他线程找到了什么候选者。
            // 备用批处理是个例外;如果我们当前正在优化备用批处理,则必须防止多个压缩相互干扰。

            // 请注意,压缩的应用是按顺序进行的。不能从多个线程调用Solver.Add和Solver.Remove。所以在多线程时,
            // 只有候选人分析实际上是多线程的。这很好--在非病理情况下,实际的按压实际上是相当罕见的！

            // 由于约束集自上次执行以来可能已任意更改,因此请从批处理向下验证。
            Debug.Assert(Solver.ActiveSet.Batches.Count > 0);
            if (nextBatchIndex >= Solver.ActiveSet.Batches.Count)
            {
                // 无效批次;换行到第一个批次。
                nextBatchIndex = 0;
                nextTypeBatchIndex = 0;
            }
            // 请注意,我们必须处理批处理具有零类型批处理的情况(因为我们还没有压缩它！)
            while (nextTypeBatchIndex >= Solver.ActiveSet.Batches[nextBatchIndex].TypeBatches.Count)
            {
                // 类型批处理无效;请移动到下一批处理。
                ++nextBatchIndex;
                if (nextBatchIndex >= Solver.ActiveSet.Batches.Count)
                    nextBatchIndex = 0;
                nextTypeBatchIndex = 0;
            }
            // Console.WriteLine($"start：Batch{nextBatchIndex},类型Batch{nextTarget.TypeBatchIndex},index{nextTarget.StartIndexInTypeBatch}");

            // 构建分析区域。
            ref var batch = ref Solver.ActiveSet.Batches[nextBatchIndex];

            // 只要对我们所需要的工作岗位数量作个慷慨的估计就行了。512在上下文中是巨大的,但在所需的短暂存储器方面微不足道。
            analysisJobs = new QuickList<AnalysisRegion>(512, pool);

            // 作业被创建为批处理类型的子集。请注意,我们从不保留部分覆盖的类型批次。这对决定论有帮助-
            // 如果我们检测到整个类型批中需要的所有压缩,则压缩列表将不会对该类型批中内存中的约束顺序敏感。
            // 虽然我们可以针对不确定的路径放松这一点,但这个阶段的成本太低,不能为一堆自定义逻辑而烦恼。
            const int targetConstraintsPerJob = 64;

            int totalConstraintsScheduled = 0;
            for (; nextTypeBatchIndex < batch.TypeBatches.Count && totalConstraintsScheduled < targetCandidateCount; ++nextTypeBatchIndex)
            {
                ref var typeBatch = ref batch.TypeBatches[nextTypeBatchIndex];
                var jobCount = 1 + typeBatch.ConstraintCount / targetConstraintsPerJob;
                var baseConstraintsPerJob = typeBatch.ConstraintCount / jobCount;
                var remainder = typeBatch.ConstraintCount - baseConstraintsPerJob * jobCount;

                var previousEnd = 0;
                analysisJobs.EnsureCapacity(analysisJobs.Count + jobCount, pool);
                for (int j = 0; j < jobCount; ++j)
                {
                    var constraintsInJob = j < remainder ? baseConstraintsPerJob + 1 : baseConstraintsPerJob;
                    ref var job = ref analysisJobs.AllocateUnsafely();
                    job.TypeBatchIndex = nextTypeBatchIndex;
                    job.StartIndexInTypeBatch = previousEnd;
                    previousEnd += constraintsInJob;
                    job.EndIndexInTypeBatch = previousEnd;
                }

                totalConstraintsScheduled += typeBatch.ConstraintCount;
            }

            // var analyzeStart=Stopwatch.GetTimestamp();
            if (threadDispatcher != null)
            {
                analysisJobIndex = -1;
                this.threadDispatcher = threadDispatcher;
                threadDispatcher.DispatchWorkers(analysisWorkerDelegate);
                this.threadDispatcher = null;
            }
            else
            {
                for (int i = 0; i < analysisJobs.Count; ++i)
                {
                    DoJob(ref analysisJobs[i], 0, pool);
                }
            }
            // var analyzeEnd=Stopwatch.GetTimestamp();

            analysisJobs.Dispose(pool);

            ref var sourceBatch = ref Solver.ActiveSet.Batches[nextBatchIndex];
            int compressionsApplied = 0;

            // var applyStart=Stopwatch.GetTimestamp();
            if (deterministic)
            {
                // 在确定性模式下,我们必须首先对每个线程找到的压缩进行排序。
                // 无论内存布局如何,按约束句柄排序都会提供唯一的顺序。
                // 当与覆盖所有类型批处理或不覆盖任何类型批处理的分析相结合时,批处理压缩器对内存布局变得不敏感,并且是确定性的。
                var totalCompressionCount = 0;
                for (int i = 0; i < workerCount; ++i)
                {
                    totalCompressionCount += workerCompressions[i].Count;
                }
                if (totalCompressionCount > 0)
                {
                    var compressionsToSort = new QuickList<CompressionTarget>(totalCompressionCount, pool);

                    for (int i = 0; i < workerCount; ++i)
                    {
                        ref var compressions = ref workerCompressions[i];
                        for (int j = 0; j < compressions.Count; ++j)
                        {
                            ref var target = ref compressionsToSort.AllocateUnsafely();
                            target.WorkerIndex = (ushort)i;
                            target.Index = (ushort)j;
                            // 请注意,我们在这里预先缓存了句柄,而不是不断地跑去从源列表中提取数据。对上下文中的性能影响不大-
                            // 从来没有太多的压缩-但它确实稍微简化了一些事情。
                            target.ConstraintHandle = compressions[j].ConstraintHandle;
                        }
                    }

                    var comparer = new CompressionComparer();
                    QuickSort.Sort(ref compressionsToSort[0], 0, compressionsToSort.Count - 1, ref comparer);

                    // 现在它们已经分类了,我们可以回去应用其中的一些。
                    // 我们可以提前停止-因为这对内存布局不敏感,我们最终会回到这些类型批,跳过一些压缩
                    // 偶尔不会有任何长期的伤害。
                    for (int i = 0; i < compressionsToSort.Count && i < maximumCompressionCount; ++i)
                    {
                        ref var target = ref compressionsToSort[i];
                        ApplyCompression(nextBatchIndex, ref sourceBatch, ref workerCompressions[target.WorkerIndex][target.Index]);
                    }

                    compressionsToSort.Dispose(pool);
                }

            }
            else
            {
                // 在非确定性模式下,我们可以按任何顺序遍历Worker结果。
                for (int i = workerCount - 1; i >= 0 && compressionsApplied < maximumCompressionCount; --i)
                {
                    ref var compressions = ref workerCompressions[i];
                    for (int j = compressions.Count - 1; j >= 0 && compressionsApplied < maximumCompressionCount; --j)
                    {
                        ApplyCompression(nextBatchIndex, ref sourceBatch, ref compressions[j]);
                        ++compressionsApplied;
                    }

                }
            }
            // var applyEnd=Stopwatch.GetTimestamp();


            // Console.WriteLine($"批次计数：{Solver.Batches.Count},压缩计数：{CompressionsApply},分析的候选项：{totalConstraintsScheduled}");
            // var analyzeTime=1e6*(analyzeEnd-analyzeStart)/Stopwatch.Frequency;
            // Console.WriteLine($"Analyze Time(Us)：{analyzeTime},Per Constraint Scheduled(Us)：{analyzeTime/totalConstraintsScheduled}");
            // var applyTime=1e6*(applyEnd-applyStart)/Stopwatch.Frequency;
            // Console.WriteLine($"Apply Time(Us)：{applyTime},Per Applicated：{applyTime/compressionsApply},(最大值：{maxumCompressionCount})");

            for (int i = 0; i < workerCount; ++i)
            {
                // 请注意：作业可能需要调整压缩计数列表中的大小。这需要使用每个员工的池。
                workerCompressions[i].Dispose((threadDispatcher == null ? pool : threadDispatcher.GetThreadMemoryPool(i)));
            }
            pool.Return(ref workerCompressions);
        }


    }
}
